//
//  Problem18.swift
//  LeetCode 18. 四数之和
//
//  Created by 武侠 on 2020/8/19.
//  Copyright © 2020 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 18. 四数之和
 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
 注意：
 答案中不可以包含重复的四元组。

 示例：
 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 满足要求的四元组集合为：
 [
   [-1,  0, 0, 1],
   [-2, -1, 1, 2],
   [-2,  0, 0, 2]
 ]
 */
class Problem18: NSObject {
    func solution() {
//            print(fourSum([1, 0, -1, 0, -2, 2], 0))
            print(fourSum([-1,0,1,2,-1,-4], -1))
//            print(fourSum([0,0,0,0], 0))
    }
    
    // 在三数之和的基础上扩展
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        var reList:[[Int]] = []
        if nums.count < 4 {
            return reList
        }
        
        let sNums = nums.sorted()
        print(sNums)
        for i in 0..<sNums.count-3 {
            // 过滤相同的值
            if i != 0 && sNums[i] == sNums[i-1] {
                continue
            }
            
            // 如果最小的4个值 相加 都>target，那么所有值，都不行
            if sNums[i] + sNums[i + 1] + sNums[i + 2] + sNums[i + 3] > target {
                break
            }
            // 如果当前的i + 最大的3个值 都<target, 那么i不合适
            if sNums[i] + sNums[sNums.count-2] + sNums[sNums.count-3] + sNums[sNums.count-1] < target {
                continue
            }
            
            var j = i+1
            while j < sNums.count - 2 {
                // 过滤相同的值
                if j != i+1 && sNums[j] == sNums[j-1] {
                    j += 1
                    continue
                }
                
                var l = j+1
                var e = sNums.count - 1
                
                // 如果最小的4个值 相加 都>target，那么所有值，都不行
                if sNums[i] + sNums[j] + sNums[l] + sNums[l+1] > target {
                    break
                }
                // 如果当前的i + j + 最大的2个值 都<target, 那么i不合适
                if sNums[i] + sNums[j] + sNums[e] + sNums[e-1] < target {
                    j += 1
                    continue
                }
                
                while l < e {
                    if sNums[i] + sNums[j] + sNums[l] + sNums[e] == target {
                        // 找到了
                        reList.append([sNums[i], sNums[j], sNums[l], sNums[e]])
                        // 此时要l++ e--, 但是需要删除重复的
                        l += 1
                        while l < e, sNums[l] == sNums[l-1] {
                            l += 1
                        }
                        
                        e -= 1
                        while l < e, sNums[e] == sNums[e+1] {
                            e -= 1
                        }
                    } else if sNums[i] + sNums[j] + sNums[l] + sNums[e] > target {
                        e -= 1
                    } else {
                        l += 1
                    }
                }
                
                j += 1
            }
        }
        
        return reList
    }
}
